#include<iostream>
#include<vector>
using namespace std;

int count = 0;

class Solution {
public:
    int reversePairs(vector<int>& nums) {
        F(nums, 0, nums.size()-1);
        return count;
    }

    void F(vector<int>& nums, int low, int high) {
        if(low >= high) {
            return;
        }
        int mid = low + (high-low)/2;
        F(nums, low, mid);
        F(nums, mid+1, high);
        merge(nums, low, mid, high);
    }

    void merge(vector<int>& nums, int low, int mid, int high) {
        int p1 = low;
        int p2 = mid+1;
        int p3 = 0;
        vector<int> tem;
        tem.resize(high-low+3);
        while(p1 <= mid && p2 <= high) {
            if(nums[p1] <= nums[p2]) {
                // tem.push_back(nums[p1++]);
                tem[p3++] = nums[p1++];
            } else {
                //打印序列
                // cout << nums[p2] << " => ";
                // for(int i = p1; i <= mid; i++) {
                //     cout << nums[i] << " ";
                // }
                // cout << endl;


                //左半区全部与nums[p2] 构成逆序对
                // tem.push_back(nums[p2++]);
                tem[p3++] = nums[p2++];
                int leftNum = mid - p1 + 1; //左半区数字数目
                count += leftNum;
            }
        }
        while(p1 <= mid) {
            // tem.push_back(nums[p1++]);
            tem[p3++] = nums[p1++];
        }
        while(p2 <= high) {
            // tem.push_back(nums[p2++]);
            tem[p3++] = nums[p2++];
        }
        for(int i = low; i <= high; i++) {
            nums[i] = tem[i-low];
        }
    }

    void test() {
        vector<int> nums = {7,5,6,4};
        int ret = reversePairs(nums);
        cout << "ret:" << ret << endl;
    }
};

int main() {
    Solution().test();
    return 0;
}